package com.julius.design.suanfa.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author julius
 * @date 2021-10-26 上午 10:09
 * <p>
 *      从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 *      https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
 * </p>
 */
public class LevelOrder {


    public static int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }

        //使用广度优先遍历算法BFS
        //按照从左到右顺序的话应该是先进先出，使用队列，每层放入，然后弹出，然后放入下一层，直到左右子树都没有了左右子树（代表着把树遍历完了）
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        //先把根节点加进去
        queue.offer(root);
        //弹出元素，是输出每一层元素的循环
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            list.add(temp.val);
            //如何把每一层元素都加进去，并将指针移动到下一层
            if(temp.left != null){
                queue.offer(temp.left);
            }
            if(temp.right != null){
                queue.offer(temp.right);
            }
        }

        //输出元素
        int[] ans = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        //[3,9,20,null,null,15,7]
        TreeNode root = new TreeNode(3);

        TreeNode root1 = new TreeNode(9);

        TreeNode root2 = new TreeNode(20);

        TreeNode root3 = new TreeNode(15);

        TreeNode root4 = new TreeNode(7);
        TreeNode root5 = new TreeNode(8);

        root.left = root1;
        root.right = root2;

        root2.left = root3;
        root2.right = root4;

        root1.left = root5;
        int[] ints = levelOrder(root);
        for (int i = 0; i <ints.length ; i++) {
            System.out.println(ints[i]);
        }
    }
}
